#include <bits/stdc++.h>
using namespace std;
//int main()
//{
//    int n;
//    cin>>n;
//    vector<bool> visited(n,true);
//    vector<vector<int>> b(n,vector<int>(n,0));
//    for(int i=0;i<n-1;i++)
//    {
//        int x,y;
//        cin>>x>>y;
//        b[x][y] == 1;
//        b[y][x] == 1;
//    }
//    for(auto i:b)
//    {
//        for(auto j:i)
//            cout<<j<<" ";
//        cout<<endl;
//    }
//}
class Graph_travel{
private:
    int capacity = 0;
    bool *visited;
    vector<list<int>> graph;
public:
    Graph_travel(int n);
    bool build_graph(int endflag);
    ~Graph_travel();
    void dfs(int node);
    void bfs(int node);
    void reset_visited();
    void show();
};
void Graph_travel::show() {
    cout<<"当前图节点数量为: "<<capacity<<"\n";
}
Graph_travel::Graph_travel(int n) {
    capacity = n;
    visited = new bool[capacity];
}
Graph_travel::~Graph_travel() {
    delete [] visited;
}
void Graph_travel::dfs(int node) {
    visited[node] = true;
    cout<<node<<" ";
    for(auto it = graph[node].begin();it != graph[node].end();++it)
    {
        if(!visited[*it])
            dfs(*it);
    }
}
void Graph_travel::bfs(int node) {
    cout<<node<<" ";
    visited[node] = true;
    queue<int> temp;
    temp.push(node);
    while(!temp.empty())
    {
        node = temp.front();
        temp.pop();

        for (auto it = graph[node].begin(); it != graph[node].end(); ++it)
            if (!visited[*it])
            {
                cout<<*it<<" ";
                temp.push(*it);
                visited[*it] = true;
            }
    }
}
bool Graph_travel::build_graph(int endflag) {
    if(capacity<=0)
        return false;
    else
    {
        for (int i = 0; i < capacity; ++i)
        {
            list<int> il;
            int t;
            while (cin >> t && t != endflag)
                il.push_back(t);
            graph.push_back(il);
            cout<<i<<" capacity:"<<capacity<<"\n";
        }
        return true;
    }
}
void Graph_travel::reset_visited() {
    memset(visited,false,sizeof(visited));
}
int main()
{
    int n;
    cout<<"请输入节点数目:"<<"\n";
    cin>>n;
    Graph_travel g = Graph_travel(n);
    g.show();
    if(g.build_graph(-1))
        g.dfs(0);
    else
        cout<<"构建邻接表图失败:"<<"\n";
}